package com.sakura.链表;

public class Code24_两两交换链表中的节点 {

    private class ListNode {
        int val;
        ListNode next;
        ListNode(int val) { this.val = val; }

        @Override
        public String toString() {
            return val + "";
        }
    }

    public static void main(String[] args) {
        ListNode node1 = new Code24_两两交换链表中的节点().new ListNode(1);
        ListNode node2 = new Code24_两两交换链表中的节点().new ListNode(2);
        ListNode node3 = new Code24_两两交换链表中的节点().new ListNode(3);
        ListNode node4 = new Code24_两两交换链表中的节点().new ListNode(4);
        node1.next = node2;
        node2.next = node3;
        node3.next = node4;
        System.out.println(new Code24_两两交换链表中的节点().swapPairs_f(node1));
    }

    // 模拟
    public ListNode swapPairs(ListNode head) {
        ListNode dummyHead = new ListNode(-1);
        dummyHead.next = head;
        ListNode cur = dummyHead;
        while (cur.next != null && cur.next.next != null) {
            ListNode first = cur.next;
            ListNode second = cur.next.next.next;
            cur.next = cur.next.next;
            cur.next.next = first;
            first.next = second;
            cur = first;
        }
        return dummyHead.next;
    }

    // 递归
    public ListNode swapPairs_f(ListNode head) {
       if (head == null || head.next == null) {
           return head;
       }
       ListNode next = head.next;
        ListNode listNode = swapPairs_f(next.next);
        head.next = listNode;
       next.next = head;
       return next;
    }
}
